package Topological;

import java.util.*;

public class CourseScheduleII {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] in = new int[numCourses]; // 记录每门课程的入度
        Map<Integer, List<Integer>> edges = new HashMap<>(); // 邻接表存图结构

        // 1.建图(构建好邻接表和每门课的入度情况)
        for(int i = 0; i < prerequisites.length; i++) {
            int a = prerequisites[i][0], b = prerequisites[i][1];
            // b -> a
            // key -> value
            if(!edges.containsKey(b)) {
                edges.put(b, new ArrayList<>());
            }
            edges.get(b).add(a); // b 的出度 + 1
            in[a]++; // a 的入度 + 1
        }

        // 2.拓扑排序
        Queue<Integer> queue = new LinkedList<>();
        //  (1) 找到入度为 0 的顶点, 放到队列中
        for(int i = 0; i < numCourses; i++) {
            if(in[i] == 0) {
                // i 的入度如果为 0, 放到队列中
                queue.offer(i);
            }
        }

        //  (2) BFS
        int[] ret = new int[numCourses];
        int index = 0;
        while(!queue.isEmpty()) {
            // 取出入度为 0 的点
            int b = queue.poll();
            // 放到结果数组中
            ret[index++] = b;
            // 删除 b 的出度(即 a 的入度)
            for(int a : edges.getOrDefault(b, new ArrayList<>())) {
                // 删除 a 的入度
                in[a]--;
                if(in[a] == 0) {
                    // 如果删除后 a 的入度变为 0, 入队列
                    queue.offer(a);
                }
            }
        }

        // 如果入度数组中存在不为 0 的元素, 说明该有向图中有环
        for(int x : in) {
            if(x != 0) {
                return new int[0];
            }
        }

        return ret;
    }
}
